package com.liuzhilong.infrastructure.framework.algorithms.algorithms;

import java.util.Arrays;
/**
 * <h1>分发糖果</h1>
 * <p>
 *     老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。
 *
 * 你需要按照以下要求，帮助老师给这些孩子分发糖果：
 *<ul>
 * <li>每个孩子至少分配到 1 个糖果。</li>
 * <li>相邻的孩子中，评分高的孩子必须获得更多的糖果。</li>
 * </ul>
 * 那么这样下来，老师至少需要准备多少颗糖果呢？
 * </p>
 */
 public class Candy {
    /**
     * 利用循环策略
     * <pre>
     *
     *     每次设置一个小朋友的糖果的时候 ，都需要遍历一下前边分配好的规则。
     *
     * </pre>
     */
    public static final class SolutionLoop {
        /**
         * @param ratings
         * @return
         */
        public int candy(int[] ratings) {
            int[] everycandy = new int[ratings.length];
            int lastScore = Integer.MIN_VALUE;
            for (int i =0;i<ratings.length;i++) {
                if(ratings[i]<=lastScore){
                    everycandy[i]=1;
                    comareAndChange(everycandy, ratings, i);
                }else {
                    if(i==0){
                        everycandy[i]=1;
                    }else {
                        everycandy[i]=everycandy[i-1]+1;
                    }
                }
                lastScore = ratings[i];

            }
            return Arrays.stream(everycandy).sum();
        }

        /**
         * @param everycandy
         * @param limit
         */
        private void comareAndChange(int[] everycandy,int[] ratings,int limit){
            if(limit==0){
                return;
            }
            if(ratings[limit]<ratings[limit-1]){
                //判断是否相同
                if(everycandy[limit]==everycandy[limit-1]){
                    everycandy[limit - 1] = everycandy[limit - 1] + 1;
                    comareAndChange(everycandy,ratings,limit-1);
                }
            }
        }


    }

    /**
     * 使用贪心算法。
     * 从左到右和从右到左两次遍历。取最大值
     */
    public static final class SolutionGreedy {
        public int candy(int[] ratings) {
            int[] left = new int[ratings.length];
            for(int i=0;i< ratings.length;i++){
                if(i!=0&&(ratings[i]>ratings[i-1])){
                    left[i]=left[i-1]+1;
                }else {
                    left[i]=1;
                }
            }
            int lastRight = 0, count = 0;
            //从右边向左遍历
            for(int i=0;i< ratings.length;i++){
                if(i!=0&&(ratings[ratings.length-i-1]>ratings[ratings.length-i])){
                    lastRight++;
                }else {
                    lastRight=1;
                }
                count += Math.max(left[ratings.length - i - 1], lastRight);
            }
            return count;
        }
    }

    public static void main(String[] args) {
        System.out.println(new SolutionLoop().candy(new int[]{1,2,87,87,87,2,1}));
        System.out.println(new SolutionGreedy().candy(new int[]{1,2,87,87,87,2,1}));
    }
}
